package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         413,
		Discription: "等差子数组的个数",
		Level:       2,
		Labels: map[string]int{
			"差分数组": 1,
			"双指针滑动":   1,
		},
	})
}

func NumberOfArithmeticSlices(nums []int) int {
	n := len(nums)
	diff := make([]int, n-1)
	//计算差分数组，略去第0个，差分数组中连续两个及以上的值相等就是等差子数组
	for i := 1; i < n; i++ {
		diff[i-1] = nums[i] - nums[i-1]
	}

	left := 0
	right := 0
	count := 0
	for right < n-1 {
		//在上一个等差子数组的基础上，left++，right不变的情况，会产生right-left个新的等差子数组（比如原本l:0.r:3,现在l++，会产生[1..3] [1..2]两（3-1）个新的子数组）
		count += right - left
		//移动right，值和left相等就+1
		for right < n-2 && diff[left] == diff[right+1] {
			right++
			count++
		}
        
		//判断是否需要移动right
		if left == right {
			right++
		}
		left++
	}

	return count
}